#include<iostream>
#include<stdio.h>

using namespace std;

//时间 O(n)  空间 O(n)
int FindMinNum(int A[], int n) {
	int ans = n + 1;
	bool* nums = (bool*)malloc(sizeof(bool) * (n + 1));
	memset(nums, 0, sizeof(bool)*(n + 1));
	for (int i = 0; i < n; ++i) {
		if (A[i] > 0 && A[i] <= n) 
			nums[A[i]] = true;
	}
	
	for (int i = 1; i <= n + 1; ++i) {
		if (!nums[i]) {
			ans = i;
			break;
		}
	}
	free(nums);
	return ans;
}

//方法二：原地交换
int FindMinNum_1(int A[], int n) {
	
	for (int i = 0; i < n; ++i) {
		while (A[i] > 0 && A[i] <= n && A[A[i]-1] != A[i]) {
			int t = A[A[i] - 1];
			A[A[i] - 1] = A[i];
			A[i] = t;
		}
	}
	for (int i = 0; i < n; ++i) {
		if (A[i] != i + 1)
			return i + 1;
	}
	return n + 1;
}

int main() {
	int A[] = { 1,2,3 };
	int n = sizeof(A) / sizeof(A[0]);
	int ans = FindMinNum(A, n);
	int ans1 = FindMinNum_1(A, n);
	cout << ans << " " << ans1;
	return 0;
}